Chris Pollett > Old Classes >
CS254
( Print View )

Student Corner:
  [Grades Sec1]

  [Submit Sec1]

  [Class Sign Up Sec1]

  [Lecture Notes]
  [Discussion Board]

Course Info:
  [Texts & Links]
  [Topics/Outcomes]
  [Outcomes Matrix]
  [Grading]
  [HW/Quiz Info]
  [Exam Info]
  [Regrades]
  [Honesty]
  [Additional Policies]
  [Announcements]

HW Assignments:
  [Hw1] [Hw2] [Hw3]
  [Hw4] [Quizzes]

Practice Exams:
  [Mid 1] [Mid 2] [Final]

HW#1 --- last modified February 10 2019 21:57:00..

Solution set.

Due date: Sep 12

Files to be submitted:
Hw1.pdf

Purpose: To refresh our memories with regard to TM, analysing algorithms, and proofs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Exhibit a simulation of one machine model with another.

Specification:

Do the following problems out of A & B: 1.1, 1.5, 1.10, 1.11.

In addition to these book questions, show the problem of determining whether the second work tape of a TM ever has the string 0110 on it during the course of its computation is undecidable. Please put all your answers to the homework problems in a pdf file Hw1.pdf. Try to make the math equations you write you readable by using a tool like LaTeX.

On the day your homework is due I will ask each group to present one problem on the board.

Point Breakdown

Five problems above (1.5 pts each - 1.5pts, completely correct; 1pt, missing minor details, 0.5pt, on the right track; 0 confused or wrong.	7.5pts
Class presentation (Write-up clear, 1.5pts; all group members could answer brief questions about the problem intelligently, 1pt).	2.5pts
Total	10pts